import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Leetcode655 {
    public static List<List<String>> printTree(TreeNode root) {
        int treeHeight = getTreeHeight(root) - 1;
        int m = treeHeight + 1;
        int n = (int) Math.pow(2, treeHeight + 1) - 1;

        List<List<String>> res = IntStream.range(0, m).mapToObj(i -> new ArrayList<>(Collections.nCopies(n, ""))).collect(Collectors.toList());

        printTree(root, res, 0, (n - 1) / 2, treeHeight);

        return res;
    }


    private static void printTree(TreeNode root, List<List<String>> res, int r, int c, int height) {
        if (root == null) {
            return;
        }

        res.get(r).set(c, String.valueOf(root.val));

        if (root.left != null) {
            printTree(root.left, res, r + 1, c - (int) Math.pow(2, height - r - 1), height);
        }

        if (root.right != null) {
            printTree(root.right, res, r + 1, c + (int) Math.pow(2, height - r - 1), height);
        }
    }

    private static int getTreeHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        return Math.max(getTreeHeight(node.left), getTreeHeight(node.right)) + 1;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        System.out.println(getTreeHeight(treeNode));
    }
}
